package cn.good.yan.sf.t6.priority;

import cn.good.yan.sf.t6.Queue;

/**
 * 6 优先级队列 - 基于 数组（无序数组） - 数组存入的元素不是按优先级排序的，是无序的
 *
 * @author shengren.yan
 * @create 2024-07-22
 */
@SuppressWarnings("all")
public class PriorityQueue1<E extends Priority> implements Queue<E> {

    Priority[] arr;
    int size = 0;

    public PriorityQueue1(int num) {
        arr = new Priority[num];
    }

    @Override
    public boolean offer(E e) {
        if (isFull()) {
            return false;
        }
        arr[size++] = e;
        return true;
    }

    @Override
    public E pool() {
        if (isEmpty()) {
            return null;
        }
        int i = getMaxIndex();
        E e = (E) arr[i];
        arr[i] = null;

        // 重新排序 , 后面的元素移动到前面
        if (i < size - 1) {
            System.arraycopy(arr, i + 1, arr, i, size - 1 - i);
        }
        size--;
        return e;
    }

    // 获取最大下标
    private int getMaxIndex() {
        int max = 0;
        for (int i = 1; i < size; i++) {
            if (arr[i].priority() > arr[max].priority()) {
                max = i;
            }
        }
        return max;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        int i = getMaxIndex();
        E e = (E) arr[i];
        return e;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == arr.length;
    }

    public static void main(String[] args) {
        PriorityQueue1<Entry> queue = new PriorityQueue1<>(6);
        // 添加元素
        queue.offer(new Entry("q1", 6));
        queue.offer(new Entry("q2", 8));
        queue.offer(new Entry("q3", 3));
        queue.offer(new Entry("q4", 5));
        queue.offer(new Entry("q5", 1));
        queue.offer(new Entry("q6", 4));
        queue.offer(new Entry("q7", 9));
        queue.offer(new Entry("q8", 10));

        System.out.println("---------------------------");
        // 1 2 3 4 5 6
        // 2 1 4 6 3 5
        // 8 6 5 4 3 1
        System.out.println("获取头元素：" + queue.peek());
        System.out.println("获取头元素：" + queue.peek());
        System.out.println("---------------------------");
        System.out.println("移除头元素：" + queue.pool());
        System.out.println("移除头元素：" + queue.pool());
        System.out.println("移除头元素：" + queue.pool());
        System.out.println("移除头元素：" + queue.pool());
        System.out.println("移除头元素：" + queue.pool());
        System.out.println("移除头元素：" + queue.pool());
        System.out.println("移除头元素：" + queue.pool());
        // q2 q1 q4 q6 q3 q5

    }

}
